package hot100;

import java.util.List;

public class Solution25 {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode slow = head;
        ListNode fast = head;
        ListNode newHead = new ListNode();
        ListNode prev = newHead;
        while (fast != null) {
            for (int i = 0; i < k; i++) {
                if (fast == null) {
                    break;
                }
                fast = fast.next;
            }
            if (fast != null) {
                prev.next = reverse(slow, fast);
                slow.next = fast;
                prev = slow;
                slow = fast;
            }
        }
        return newHead;
    }

    private ListNode reverse(ListNode head, ListNode tail) {
        ListNode newHead = new ListNode();
        while (head != tail) {
            ListNode tmp = newHead.next;
            newHead.next = head;
            head = head.next;
            newHead.next.next = tmp;
        }
        return newHead.next;
    }

    public static void main(String[] args) {
        Solution25 solution25 = new Solution25();
        ListNode head = new ListNode(1);
        ListNode p = head;
        p.next = new ListNode(2);
        p = p.next;
        p.next = new ListNode(3);
        p = p.next;
        p.next = new ListNode(4);
        p = p.next;
        p.next = new ListNode(5);
        solution25.reverseKGroup(head, 2);
    }
}

class ListNode {

    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    public static ListNode generateList(int[] arr) {
        ListNode newHead = new ListNode();
        ListNode p = newHead;
        for (int i : arr) {
            p.next = new ListNode(i);
            p = p.next;
        }
        return newHead.next;
    }
}